package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
 *
 * 在比较时，字母是依序循环出现的。举个例子：
 *
 * 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test744 {

    public char nextGreatestLetter(char[] letters, char target) {
        int i = 0;
        int j = letters.length-1;
        if (letters[0] > target){
            return letters[0];
        }
        if (letters[j] <= target){
            return letters[0];
        }
        while (i<=j){
            int mid = i + (j-i) /2 ;
            if (letters[mid] == target) i = mid+1;
            if (letters[mid] <target) i = mid+1;
            if (letters[mid] > target){
                if (letters[mid-1]<=target){
                    return letters[mid];
                }else {
                    j = mid-1;
                }
            }
        }
        return '1';
    }
}
